package advanced.class_append;

import java.util.Stack;

/**
 *
 * 左神算法进阶班第三课————单调栈
 * 难度——顶尖
 * 问题描述：
 *      指定一个数组arr；
 *      数组的中元素的含义为一个环形山脉每座山的高度；
 *      规定，相邻的两座山脉之间可以彼此看见；
 *      如果两座山脉不相邻，两座山脉之间的所有山脉不大于这两座山脉的最小值时，这两座山脉可以互相看见。
 *      现在希望你可以求出可以彼此看见的山脉总对数。
 *
 */
public class Code_03_CircleMountain {

    static class Pair{
        int value;    // 存放当前山峰的高度，就是数组中某个位置的值
        int times = 1;    // 当前山峰已经出现的次数，也就是数组中某个位置元素出现的次数，初始化为1

        Pair(int value) {
            this.value = value;
        }
    }

    /**
     * 主函数入口，获取彼此可以相互看见的最大山峰对
     * @param arr
     * @return
     */
    public static long communications(int[] arr) {
        if(arr == null || arr.length == 0) {
            return 0;
        }
        int size = arr.length;
        //-----更新出数组中最大元素的索引-----
        int maxIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            maxIndex = arr[maxIndex] < arr[i] ? i : maxIndex;
        }
        int value = arr[maxIndex];
        int index = nextIndex(size,maxIndex);
        long res = 0L;
        //-----创建单调栈的结构-----
        Stack<Pair> stack = new Stack<Pair>();
        //----首先将数组中最大的元素扔进栈中----
        stack.push(new Pair(value));
        while(index != maxIndex){
            value = arr[index];
            // 如果栈不为空，且当前遍历到的元素大于栈顶的元素值，那么此处要更新res，可以增加山峰对了
            while(!stack.isEmpty() && stack.peek().value < value) {
                int times = stack.pop().times;
                res += getInternalSum(times) + (2 * times);
            }
            if(!stack.isEmpty() && stack.peek().value == value){
                stack.peek().times++;
            }else{
                stack.push(new Pair(value));
            }
            index = nextIndex(size,index);
        }
        // 当栈不为null时，继续遍历
        while(!stack.isEmpty()){
            int times = stack.pop().times;
            res += getInternalSum(times);
            if(!stack.isEmpty()){
                // 首先加上一个times
                res += times;
                if(stack.size() > 1){
                    //如果栈中剩余并不是最大的值，那么再加一个times,左右都可以找到最大的山峰
                    res += times;
                } else{
                    // 否则，如果最大的山峰只有一个，那么只需要加一次times即可
                    res += stack.peek().times > 1 ? times : 0;
                }
            }
        }
        return res;
    }

    /**
     * 获取环中当前位置的下一元素的索引
     * @param size
     * @param maxIndex
     * @return
     */
    private static int nextIndex(int size, int maxIndex) {
        return maxIndex == size - 1 ? 0 : maxIndex + 1;
    }

    /**
     * 获取连续times相等的山峰可以构成有效山峰对的数量
     * @param times
     * @return
     */
    private static long getInternalSum(int times) {
        return times == 1L ? 0 : (long)times * (long)(times - 1) / 2L;
    }

    // 测试函数
    public static void main(String[] args) {
        int[] arr = {1,2,3,3,3,4,4,5,5,6};
        System.out.println(communications(arr));
    }
}
